Asynchronous transfer mode (ATM) networks and other communication networks comprise an array of switching nodes and interconnecting communication links. As known, there are certain costs or characteristics associated with the transfer of information through a tandem of such switching nodes and connected links. Some of these characteristics, for example, fixed delay, delay variation, and administrative weight, are cumulative. For these characteristics, sometimes referred to as "metrics", an optimal path is conventionally defined as one in which the set of tandem switching nodes and links produces the smallest cumulative value.
Other characteristics, such as bandwidth and cell loss ratio are, respectively, minimum determinative and maximum determinative of the corresponding characteristics of a path and essentially define a bottleneck. These characteristics are called "attributes". An optimal path with respect to a minimum determinative attribute such as bandwidth, is one that exhibits the largest bottleneck value along the path. An optimal path with respect to a maximum determinative attribute such as cell loss ratio is one that exhibits the smallest bottleneck value along the path. As metrics and attributes can vary from one switching node and connected link to another, there is a need to determine a path through a network that is optimal with respect to each metric and attribute, such an optimal path minimizing a metric or either maximizing or minimizing an attribute, as appropriate.
In one prior art approach, a graph for a particular characteristic, e.g., fixed delay, is defined in which a switching node is called a "vertex" and each communications link is called an "edge" that has a defined particular value. With networks comprising only a few switching nodes and communication links, a memory at each switching node can readily and practically include information about all possible paths through the network. This path information is generally produced during initialization, upon any restructuring of the network or upon any change in the network that might be caused by a failure of a particular switching node.
Today's networks, however, are increasing in both complexity and size. In ATM networks, particularly, the concept of having sufficient information at each switching node to describe optimal paths to all other switching nodes for each metric and attribute becomes unmanageable. An alternative approach defines a hierarchical network. In this approach subsets of switching nodes and communications links are arbitrarily grouped into subnetworks or "peer groups". A single logical representation, known as a logical group node, is then produced for each subnetwork or peer group. An arbitrary subset of the logical representations or logical group nodes may further be grouped into a subnetwork or peer group for the next higher level of the hierarchy. Such grouping may be repeated for an arbitrary number of levels.
In a hierarchical network, certain switching nodes in a peer group (or logical group nodes if the peer group is not at the lowest level of the hierarchy) may be connected either to other switching nodes or to logical group nodes outside the peer group; that is, they may be connected to switching nodes in other peer groups. Within a peer group, such switching nodes with external connections are referred to as border switching nodes. Switching nodes that connect only to switching nodes within the same peer group are referred to as interior switching nodes. In essence, a general approach is to obtain a representation of an optimal path for each metric and attribute between each pair of border switching nodes.
It has further been the practice to attempt to produce a topology representation of the connectivity between border switching nodes in peer groups in which the information is aggregated and compressed to reduce the quantity of data that must be retained at different switching nodes to support efficient routing from a remote source to a switching node in a peer group or through the peer group to reach a remote destination. U.S. Pat. No. 5,535,195 (1996) to the same inventor as this invention, discloses one such method for aggregating attributes, namely bandwidth, in which a peer group or subnetwork with a symmetrical bandwidth (i.e., the bandwidth is the same in both directions of a link) is converted to a full mesh virtual topology. Then a spanning tree virtual topology is generated based upon the full mesh topology for being advertised by a subnetwork leader that will typically be one of the border switching nodes. While this approach successfully represents the topology in terms of a symmetrical attribute to be maximized, it has not been found to be readily adapted in other applications, such as the representation of a subnetwork or peer group in terms of an asymmetrical attribute or a metric.
"Data Networks", Dimitri Bertsekas & Robert Gallager, Prentice Hall, 1987 (pg. 322-325) describes two well known shortest path algorithms, or methodologies, which can be used to generate a shortest path between each pair of border switching nodes in a peer group, thereby obtaining, for the peer group, topology representation in the form of a full mesh graph spanning the border switching nodes. The so-called Dijkstra methodology finds the shortest path in order of increasing path length from one node to all other nodes in the network or peer group. This approach has a computational complexity of the order N.sup.2 per shortest path where N represents the total number of switching nodes in a subnetwork including border and interior switching nodes. The so-called Floyd-Warshall methodology finds the shortest path between all pairs of nodes collectively in an iterative procedure that evaluates sets of nodes that are allowed as intermediate nodes in the various paths. The Floyd-Warshall methodology has a computational complexity of an order of magnitude of N.sup.3, where N again represents the total number of switching nodes in a subnetwork including both border and interior switching nodes.
Graph spanners are disclosed in "Graph Spanners", David Peleg & Alejandro A. Schaffer, Graph Spanners, Graph Theory, Vol. 13, No. 1, (pg. 99-116) for generating a topology representation in the form of an aggregation of connectivity information. "On Sparse Spanners of Weighted Graphs", Ingo Althofer, Gautam Das, David Dobkin, Deborah Joseph & Jose Soares, Discrete Computational Geometry, Vol. 9, 1993 (pg. 81-100) discloses an approach for compressing a spanner graph subject to an upper bound on a stretch factor. According to this approach a subgraph or subnetwork is said to be a "t-spanner" if, between any pair of vertices the distance in the subgraph is at most "t" times longer than the distance in the original graph. The value of "t" is the stretch factor associated with the subgraph.
Values of "t" greater than one indicate that some information about the peer group has been lost, so certain details about the paths can not be determined This approach scans the edges of a given graph in order of nondecreasing metric values or weights. At each iteration the scanned edge is selected if there exists no alternate path in the subgraph of selected edges, such that the alternate path is shorter than or equal to t times the weight of the scanned edge. When all the edges have been scanned, the subgraph of selected edges gives a t-spanner for the original graph. While this approach successfully determines a topology representation in the form of a lossless compressed form for a peer group by letting the stretch factor assume the value of one, it is applicable only when all the switching nodes in the original topology are border nodes.
In accordance with another approach, a topology representation exists in the form of a star whose center does not correspond to any vertex in the original graph. The most primitive approach is using a star to assign a common metric value to each edge connecting the center vertex to a border vertex. A more sophisticated approach is to allow different metric values to be assigned to these edges. All existing approaches based on the star representation generally do not support graph compression subject to a stretch factor of "one" except in very special cases.
Generally, therefore, the prior art has suggested various approaches for generating a compressed aggregation that represents the topology of a peer group. In some, the maximum compression of the graph, and hence the minimization of topology information to be advertised, generates a stretch factor that is greater than one. Other approaches, while effective in some applications, have not been generally applicable for generating an aggregation for both metrics and attributes. Yet in other approaches, all nodes within a topology to be aggregated are necessarily border nodes, and there is no obvious generalization of the approaches to generate an aggregated topology for a peer group where only a subset of all nodes in the peer group are border nodes. Moreover, attempts to compress the data describing the effect of a metric or attribute has provided an inaccurate representation of the paths through a peer group.
Accordingly, there remains a need for a method for determining topology representation in the form of a lossless compressed aggregation of optimal paths in a subnetwork in a communication network, such that all the topology information that is pertinent to routing through the subnetwork is retained.